package 力扣_树算法.路径;

/**
 * @author zx
 * @create 2022-09-12 20:31
 * https://leetcode.cn/problems/binary-tree-maximum-path-sum/solution/shou-hui-tu-jie-hen-you-ya-de-yi-dao-dfsti-by-hyj8/
 *
 * 和(543.二叉树的直径)有点像,参考上面的思路,AI修改了代码
 */
public class 二叉树中的最大路径和_124 {

    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }
    /**
     * 函数功能：返回当前节点能为父亲提供的贡献,需要结合上面的图来看！
     */
    private int dfs(TreeNode root) {
        // 如果当前节点为叶子节点,那么对父亲贡献为0
        if (root == null) {
            return 0;
        }
        // 计算左右子节点的贡献值;如果贡献小于0的话,直接返回0即可！
        int left = Math.max(dfs(root.left), 0);
        int right = Math.max(dfs(root.right), 0);
        // 更新最大路径和结果
        res = Math.max(res, root.val + left + right);
        // 返回当前节点能为父节点提供的最大贡献值
        return root.val + Math.max(left, right);
    }
}
